package sort;

import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.Random;

public class Sort {
    @Test
    public void test(){

        int[] list={1,3,4,5,2,0};
        show(list);
        heapSort1(list);
        show(list);
//

//        int[] list = getArray(80000);
//        System.out.println("排序前:");
//        System.out.println("开始时间:" + getCurrentTime());
//        System.out.println("排序后:");
//        heapSort1(list);
//        System.out.println("结束时间:" + getCurrentTime());
//        八百万个数据一秒
//        heapSort1(list);
//        堆排序花费5秒
//        heapSort(list)
//        基数排序大概十分之一秒
//        radixSort(list,3);
//        归并排序不到一秒
//        mergeSort(list,0,list.length-1);
        //快速排序花费时间不足一秒
        //quickSort(list,0,list.length-1);
        // 移动式希尔排序花费不足一秒
        // shellSort2(list);
        //交换式希尔排序花费11秒
        //shellSort(list);
        //插入排序花费1秒
        //int[] array = insertionSort(list);
        //选择排序花费四秒
        //int[] array = selectionSort(list);
        //冒泡排序八万个数据,12秒
        //bubbleSort(list);
        //show(array);
    }
    /**
     * 正宗堆排序
     * @param list 待排序的数组
     */
    public void heapSort1(int[] list){
         for (int i= list.length/2-1;i>=0;i--){
             adjustHeap1(list,i,list.length);
         }
         int len=list.length-1;
         int temp;
          while(len>=0){
              temp=list[0];
              list[0]=list[len];
              list[len]=temp;
              adjustHeap1(list,0,len);
              len--;
          }
    }

    /**
     * 将以i为根节点的子树调整为大顶堆
     * @param list 欲排序的序列
     * @param i 根节点
     * @param len 要调整的边界
     */
    private void adjustHeap1(int[] list,int i,int len) {
      int j;//左孩子

      int k=2*i+1;
      int root=list[i];
      while(k<len){
          if ( k+1<len && list[k + 1] > list[k]) {
               k++;
           }
           if (list[k] > root) {
               list[i] = list[k];
               i=k;
               k=k*2+1;
           } else {
               //左右孩子不大于当前节点,说明当前子数正确直接退出
               break;
           }
       }
       list[i]=root;
       /* for ( j=2*i+1; j < len; j=j*2+1) {
            if( j+1<len && list[j+1]>list[j]){
                j++;
            }
            if (root<list[j]){
                list[i]=list[j];
            }
            i=j;
        }
        list[i]=root;*/
    }
    /**
     * 自我写的堆排序,从小到大,效率低下,能量不足
     */
    public void heapSort(int[] list){
        if (list.length==0)
            return;
        int temp;
        int len=list.length-1;
        while(len>=1){
            adjustHeap(list,list.length/2-1,len);
            //show(list);
            temp=list[len];
            list[len]=list[0];
            list[0]=temp;
            //show(list);
            len--;
        }
     }

    /**
     * 用于将现有堆调整为大顶堆
     * @param list 待排序的数组
     * @param i 第i个非叶子节点,最后一个非叶子节点=length/2-1
     * @param length 待数组的长度,会随着排序的进行逐渐缩减
     */
     private void adjustHeap(int[] list,int i,int length){
         int current;
         int temp;
         while(i>=0){
            //左节点2*i+1,右节点2*i+2
            if (2*i+1<=length){
                if (list[i]<list[2*i+1]){
                    temp=list[i];
                    list[i]=list[2*i+1];
                    list[2*i+1]=temp;
                }
            }
           if (2*i+2<=length){
               if(list[i]<list[2*i+2]){
                   temp=list[i];
                   list[i]=list[2*i+2];
                   list[2*i+2]=temp;
               }
           }
            i--;
        }
     }
    /**
     * 此函数用于实现基数排序
     * @param list 用于排序的数据列表
     * @param highest list中的最大数据的位数
     * @return 排序好的数组
     */
    private int[] radixSort(int[] list,int highest){
        //创建十个桶,由于桶排序先进后出的特征,用栈代替
        ArrayList<Integer> one = new ArrayList<>();
        ArrayList<Integer> two = new ArrayList<>();
        ArrayList<Integer> three = new ArrayList<>();
        ArrayList<Integer> four = new ArrayList<>();
        ArrayList<Integer> five = new ArrayList<>();
        ArrayList<Integer> six = new ArrayList<>();
        ArrayList<Integer> seven = new ArrayList<>();
        ArrayList<Integer> eight = new ArrayList<>();
        ArrayList<Integer> nine = new ArrayList<>();
        ArrayList<Integer> zero = new ArrayList<>();
        for (int i=1;i<=highest;i++){
            for (int j = 0; j < list.length; j++) {
                int s = takenumber(list[j], i);//取list[j]的第i位数字(从个位开始)
                switch(s){
                    case 0: zero.add(list[j]);
                        break;
                    case 1: one.add(list[j]);
                        break;
                    case 2: two.add(list[j]);
                        break;
                    case 3: three.add(list[j]);
                        break;
                    case 4: four.add(list[j]);
                        break;
                    case 5: five.add(list[j]);
                        break;
                    case 6: six.add(list[j]);
                        break;
                    case 7: seven.add(list[j]);
                        break;
                    case 8: eight.add(list[j]);
                        break;
                    case 9: nine.add(list[j]);
                        break;
                }
            }
            //一趟装桶完成,然后将桶中数据取出装回原数组
            int index=0;
            for (int k=0;k<zero.size();k++){
                list[index++]=zero.get(k);
            }
            zero.clear();
            for (int k=0;k<one.size();k++){
                list[index++]=one.get(k);
            }
            one.clear();
            for (int k=0;k<two.size();k++){
                list[index++]=two.get(k);
            }
            two.clear();
            for (int k=0;k<three.size();k++){
                list[index++]=three.get(k);
            }
            three.clear();
            for (int k=0;k<four.size();k++){
                list[index++]=four.get(k);
            }
            four.clear();
            four.clear();
            for (int k=0;k<five.size();k++){
                list[index++]=five.get(k);
            }
            five.clear();
            for (int k=0;k<six.size();k++){
                list[index++]=six.get(k);
            }
            six.clear();
            for (int k=0;k<seven.size();k++){
                list[index++]=seven.get(k);
            }
            seven.clear();
            for (int k=0;k<eight.size();k++){
                list[index++]=eight.get(k);
            }
            eight.clear();
            for (int k=0;k<nine.size();k++){
                list[index++]=nine.get(k);
            }
            nine.clear();
        }


        return list;
    }
    /**
     * 此方法用于取出特定位数的数字
     * @param no 1代表各位,2代表十位,以此类推
     * @param number 欲取相应数位数的数字
     * @return no位的数值
     */
    private int takenumber(int number,int no){
        int temp=-1;
        for (int i = 0; i < no; i++) {
            //对10取余数一次为个位,去零除十,再取余为十位........
            temp=number%10;
            number/=10;
        }
        return temp;
    }
    private int[] mergeSort(int[] list,int left,int right){
        int middle=(right+left)/2;
        if (left<right){
            //左边递归
            mergeSort(list,left,middle);
            //右边递归
            mergeSort(list,middle+1,right);
        }
        merge(list,left,right);
        return list;
    }
    private void merge(int[] list,int left,int right){
        int middle=(left+right)/2;
        int ltemp=left;//左边数组的指针
        int rtemp=middle+1;//右边数组的指针
        int btemp=0;//缓存数组的指针
        int length=right-left+1;//缓存数组长度
        int[] buffer=new int[length];
        //left到middle为左边数组,middle+1到right为右边数组
      int i=0;
      while(ltemp<=middle && rtemp<=right ){
          if(list[ltemp]<=list[rtemp]){
              buffer[i++]=list[ltemp];
              ltemp++;
          }else{
              buffer[i++]=list[rtemp];
              rtemp++;
          }
      }
      if (rtemp<=right){
          //左边的数组完结了,将右边的数据全部挪到缓冲数组中
          while(rtemp<=right){
              buffer[i++]=list[rtemp++];
          }
      }else{
          while(ltemp<=middle){
              buffer[i++]=list[ltemp++];
          }
      }//将缓冲数组中的数据挪到原数组
        ltemp=left;
        rtemp=right;
        int temp=0;
        for (int j = ltemp; j <=rtemp ; j++) {
            list[j]=buffer[temp++];
        }
    }
    private  int[] quickSort(int[] list,int l,int r){

        int right=r;//左指针
        int left=l;//右指针
        //int temp;//用于交换的临时变量
        if (left>right){
            return null;
        }
        int pivot=list[left];//将首元素作为中心轴
        //记得写出递归条件

        while(left<right){
            while (left <right && list[right]>pivot){
                right--;
            }
            if (left<right){
                //找到结果了,(右指针所指数小于中轴值)
                list[left]=list[right];
                left++;
            }
            while(left<right && list[left]<pivot){
                left++;
            }
            if (left<right){
                //左指针所指值大于中轴
                list[right]=list[left];
            }
        }
        if (left>=right){
            list[left]=pivot;
        }
       // show(list);
        //递归左边
        quickSort(list,l,left-1);
        //递归右边
        quickSort(list,right+1,r);
        return list;
    }
    private int[] shellSort2(int[] list){
        //插入式的希尔排序
        for (int step=list.length/2;step>=1;step/=2){
            for (int i=step;i<list.length;i++){
                int j=i;
                int temp=list[j];
                while(j-step>=0 && temp<list[j-step]){
                    list[j]=list[j-step];
                    j-=step;
                }
                list[j]=temp;
            }
          //  show(list);
        }

        return list;
    }
    private int[] shellSort(int[] list){
       //希尔排序旨在快速建立比较有序的序列

        System.out.println("-------------交换式希尔排序---------------");
        //交换式的希尔排序
        int temp;

        for(int step=list.length/2;step>=1;step/=2){
             //希尔排序的每一轮内循环并不能使一个分组完全有序,只能做到大致有序
            for(int i=step;i<list.length;i++){
                //i=step第一个分组的第二个元素,由于考虑到奇数的问题因此要从此处开始遍历至末尾
                //System.out.println("当前步长:"+step);
                for (int j= i-step; j>=0;j-=5){
                    //从第j个位置,也就是开头开始将同组相邻元素进行比较,将较小的元素,换到前面
                    if (list[j]>list[j+step]){
                        temp =list[j];
                        list[j]=list[j+step];
                        list[j+step]=temp;
                    }
                    //System.out.println("i:"+i+"   "+"j:"+j);
                    //show(list);
                }
            }

//            show(list);
         }

        return list;
    }
    private int[] insertionSort(int[] list){
        for (int i = 1; i < list.length; i++) {
            int current=list[i];
            int j=i-1;
            for (;j>=0;j--){
                if (list[j]<current){
                    //当前数字大于j位数字,需要将当前数字插在j+1位
                    break;
                }
            }
            //也就是将j+1至i-1位从后往前一次后移一个单位
            for(int k=i-1;k>=j+1;k--){
                list[k+1]=list[k];
            }
            list[j+1]=current;
//            show(list);
        }

        return list;
    }
    private int[] selectionSort(int[] list){
        //选择排序即每次大循环都会找出一个最小(大)的数,然后放在对应位置
           //选择排序进行n-1次大循环
        for (int i = 0; i < list.length-1; i++) {
            //每次小循环负责找出最小的一个数,然后放在前面,然后下次内循环遍历其余数
            //假定当前数据就是最小
              int min=list[i];
              int minLocation=i;
            for (int j = i+1; j <list.length ; j++) {
                if (list[j]<min){
                    //如果当前数字小于min,则先保存当前数字的值和位置,放到,内循环结束去比较
                    min=list[j];
                    minLocation=j;
                }
            }
            //当一次内循环结束,将找到的最小值与前面的数字互换
            int temp=list[i];
            list[i]=min;
            list[minLocation]=temp;
        }
        return list;
    }
    private int[] bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
             boolean flag=false;
             for (int j = 0; j <array.length-i-1 ; j++) {
                if (array[j]>array[j+1]){
                    flag=true;
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
             if (!flag){
                 break;
             }
        }
        return array;
    }


    private int[] getArray(int maxsize){
        int[] ints = new int[maxsize];
        for (int i=0;i<maxsize;i++){
            Random random = new Random();
            int nextInt = random.nextInt(100);
            ints[i]=nextInt;
        }
        return ints;
    }
    private void  show(int[] array){
        for (int i = 0; i < array.length; i++) {
            if (i%5==0 && i!=0)
                System.out.print("|"+array[i]+" ");
            else
                System.out.print(array[i]+" ");
        }
        System.out.println("");
    }
    public static String getCurrentTime(){
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date);
        return format;
    }
}
